﻿P10387[蓝桥杯 2024 省 A] 训练士兵

在蓝桥王国中，有 n 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 i 名士兵来说，进行一次训练所需的成本为 p
i
​
枚金币，而要想成为顶尖战士，他至少需要进行 c
i
​
次训练。
为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 S 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。
作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵都成为顶尖战士？

输入格式
输入的第一行包含两个整数 n 和 S，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。
接下来的 n 行，每行包含两个整数 p
i
​
和 c
i
​
，用一个空格分隔，表示第 i 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。

输出格式
输出一行包含一个整数，表示使所有士兵成为顶尖战士所需的最少金币数。

输入输出样例
输入 #1复制
3 6
5 2
2 4
3 2
输出 #1复制
16


//思路：简单贪心：只要符合剩下没完成的士兵的单次训练总和rs大于S就去群体训练（不过要注意随着群体训练次数的增加这个rs会变小的；及时更新）
//因此可以这样看 cnt[i]-->rs   rs S sum共同促使ans成立

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
long long n, S;//士兵个数，团体训练的金币数
long long remainone_summon;//还可以训练的士兵每个人完成一次训练的金币总和
long long sum;//单独训练这些士兵花费的总金币
const int N = 1e6 + 5;
long long cnt[N];//记录相同训练次数后完成的士兵；的训练一次的金币总和
long long ans;
void solve() {
    cin >> n >> S;
    //初始化完准备数据：
    for (int i = 1; i <= n; i++) {
        long long x, y;//训练一次士兵的金币个数x；需要y次训练；没有超范围还要longlong？
        cin >> x >> y;
        remainone_summon += x;
        sum += x * y;//总计好单次总的sum方便后面ans+sum
        cnt[y] += x;  //方便进行几次群体训练后得到新的remainone_summon
    }
    //试探可以轮多少次团体训练：
    for (int i = 1; i < N; i++) {
        if (remainone_summon < S)  break;//剩下的都去单独训练
        ans += S;
        sum -= remainone_summon;//进行了群体训练相当于剩下没训练完的士兵各完成一次训练；因此减去单次训练的总金币数
        remainone_summon -= cnt[i];//及时更新remainone_summon
    }
    ans += sum;
    cout << ans << endl;
}
int main() {

    IOS;
    solve();
    return 0;
}


